首页 > 试题广场 >

编辑距离(一)

[编程题]编辑距离(一)
  • 热度指数：23808 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定两个字符串 str1 和 str2 ，请你算出将 str1 转为 str2 的最少操作数。
你可以对字符串进行3种操作：
1.插入一个字符
2.删除一个字符
3.修改一个字符。

字符串长度满足 ，保证字符串中只出现小写英文字母。
示例1

输入

"nowcoder","new"

输出

6

说明

"nowcoder"=>"newcoder"(将'o'替换为'e')，修改操作1次
"nowcoder"=>"new"(删除"coder")，删除操作5次
示例2

输入

"intention","execution"

输出

5

说明

一种方案为:
因为2个长度都是9，后面的4个后缀的长度都为"tion"，于是从"inten"到"execu"逐个修改即可
示例3

输入

"now","nowcoder"

输出

5
算法知识视频讲解
添加回答
Python 3
Songlin2023头像 Songlin2023 
class Solution:
    def editDistance(self , s1: str, s2: str) -> int:
        # write code here
        n1=len(s1)
        n2=len(s2)
        #dp[i+1][j+1]为s1[0..i]到s2[0...j]的最少操作数
        dp = [[0]*(n2+1) for _ in range(n1+1)]
        #确定初始值
        for j in range(n2+1):
            dp[0][j]=j
        for i in range(n1+1):
            dp[i][0]=i
        #状态转移
        for i in range(1,n1+1):
            for j in range(1,n2+1):
                if s1[i-1]==s2[j-1]:
                    dp[i][j]=dp[i-1][j-1]
                else:
                    #[i][j],由于i和j-1匹配，i处插得到新的i，至j匹配
                    #[i][j],由于i-1和j匹配，i处删，至i-1匹配
                    #替换,由于i-1和j-1匹配，i处替换成j
                    dp[i][j] = min(dp[i][j-1]+1,  \
                                   dp[i-1][j]+1,  \
                                   dp[i-1][j-1]+1)
        return dp[n1][n2]

发表于 2022-08-26 10:25:07 回复(0)
Python 3
蓝鲸与风头像 蓝鲸与风 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param str1 string字符串 
# @param str2 string字符串 
# @return int整型
#
class Solution:
    def editDistance(self , str1: str, str2: str) -> int:
        # write code here
        m=len(str1)
        n=len(str2)
        dp=[[0]*(n+1) for i in range(m+1)]
        #第一行
        for i in range(n+1):
            dp[0][i]=i 
        #第一列
        for i in range(m+1):
            dp[i][0]=i 
        for i in range(1, m+1): 
            for j in range(1,n+1):
                if str1[i-1]==str2[j-1]:   
                    dp[i][j]=dp[i-1][j-1]
                else:
                #可以是删除，添加，修改
                #替换dp[i-1][j-1] 删除dp[i-1][j] 添加dp[i][j-1]
                    dp[i][j]=min(min(dp[i][j-1],dp[i-1][j]),dp[i-1][j-1])+1
        print(dp)
        return dp[m][n]

发表于 2022-08-22 11:17:23 回复(0)
Python 3
在研究求职打法的香菇头像 在研究求职打法的香菇 
class Solution:
    def editDistance(self , str1: str, str2: str) -> int:
        # write code here
        n = len(str1)
        m = len(str2)
        # n+1行 m+1列 [0][0]为空字符
        dp = [[0 for j in range(m+1)] for i in range(n+1)]
        # 第一行： 空字符转化为 str2 所需最少操作数
        for j in range(m+1):
            dp[0][j] = j
        # 第一列： str1转化为 空字符 所需最少操作数
        for i in range(n+1):
            dp[i][0] = i
        for i in range(1, n+1):
            for j in range(1, m+1):
                # dp[i][j]：将str1[:i]全部修改为str2[:j]所需最小操作数(右闭)
                if str1[i-1] == str2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    # 插入：先完成调整使str1[:i]=str2[:j-1]，str1末尾再插入str2[j]
                    insert = dp[i][j-1] + 1
                    # 删除：先完成调整使str1[:i-1]=str2[:j]，再删除str1[i]
                    remove = dp[i-1][j] + 1
                    # 修改：先完成调整使str1[:i-1]=str2[:j-1]，再修改str1[i]=str2[j]
                    change = dp[i-1][j-1] + 1
                    
                    dp[i][j] = min(insert, remove, change)
        return dp[-1][-1]


发表于 2022-08-20 16:43:12 回复(0)
Python 3
Vivimore头像 Vivimore

经典动态规划
先把s1=[]和s2=[]的边界位置先填充，再填充中间位置
时间复杂度：O(mn) 空间复杂度：O(mn)

class Solution:
    def editDistance(self , str1: str, str2: str) -> int:
        n = len(str1)
        m = len(str2)
        dp = [[0]*(m+1) for i in range(n+1)]
        for i in range(1, n+1):
            dp[i][0] = dp[i-1][0] + 1
        for j in range(1, m+1):
            dp[0][j] = dp[0][j-1] + 1
        for i in range(1, n+1):
            for j in range(1, m+1):
                if str1[i-1] == str2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
        return dp[n][m]
发表于 2022-06-23 09:48:31 回复(0)
Python 3
牛客344707077号头像 牛客344707077号 
class Solution:
    def editDistance(self , str1: str, str2: str) -> int:
        # write code here
        if not str1:
            return len(str2)
        if not str2:
            return len(str1)
        dp = [[0 for i in range(len(str2)+1)] for j in range(len(str1)+1)]
        for i in range(1,len(str1)+1):
            dp[i][0] = i
        for j in range(1,len(str2)+1):
            dp[0][j] = j
        for i in range(1,len(str1)+1): 
            for j in range(1,len(str2)+1):
                if str1[i-1]==str2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1#改，删，增
        return dp[len(str1)][len(str2)]

发表于 2022-05-11 19:24:30 回复(0)
Python 3
想搞机器学习的小白头像 想搞机器学习的小白 
class Solution:
    def editDistance(self , str1: str, str2: str) -> int:
        # write code here
        m,n =len(str1),len(str2)
        dp = [[0]*(n+1) for _ in range(m+1)]
        #初始化，预留空串
        for i in range(m+1):
            dp[i][0] = i
        for j in range(n+1):
            dp[0][j] = j
        for i in range(1,m+1):
            for j in range(1,n+1):
                if str1[i-1]!=str2[j-1]:
                    dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
                else:
                    dp[i][j] = dp[i-1][j-1]
        return dp[m][n]

发表于 2022-04-28 19:23:30 回复(0)
提交观点

问题信息

动态规划 字符串
难度：
12条回答 3720浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号